package com.lzq.leetcode.hoot100;

import java.util.ArrayList;
import java.util.List;

public class s51 {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        dfs(n, 0, new int[n], ans);
        return ans;
    }

    private void dfs(int n, int row, int[] board, List<List<String>> ans) {

        // 终止
        if (row == n) {
            List<String> boardStrList = new ArrayList<>();
            StringBuilder builder = new StringBuilder();
            for (int i=0; i<n; i++) {
                builder.delete(0, builder.length());
                for (int j=0; j<n; j++) {
                    builder.append( j == board[i] ? 'Q' : '.');
                }
                boardStrList.add(builder.toString());
            }
            ans.add(boardStrList);
            return;
        }

        for (int i=0; i<n; i++) {
            // 判断是否可行
            boolean avaliable = true;
            for (int r=0; r<row; r++) {
                if (i == board[r] || row - r == Math.abs(i - board[r])) {
                    avaliable = false;
                    break;
                }
            }
            if (!avaliable) continue;
            // 添加到棋盘
            board[row] = i;
            dfs(n, row+1, board, ans);
        }
    }

    public static void main(String[] args) {
        s51 s51 = new s51();
        System.out.println(s51.solveNQueens(4));

    }
}
